package com.bupt.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution1 {
	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> results = new ArrayList<Integer>();
		spirals(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1, results);
		return results;
	}

	public void spirals(int[][] matrix, int sx, int sy, int ex, int ey,
			List<Integer> results) {
		if (sx > ex || sy > ey)
			return;
		if (sx == ex) {
			for (int j = sy; j <= ey; j++) {
				results.add(matrix[sx][j]);
			}
			return;
		}
		if (sy == ey) {
			for (int i = sx; i <= ex; i++) {
				results.add(matrix[i][sy]);
			}
			return;
		}
		for (int j = sy; j <= ey; j++) {
			results.add(matrix[sx][j]);
		}
		for (int i = sx + 1; i <= ex; i++) {
			results.add(matrix[i][ey]);
		}
		for (int j = ey - 1; j > sy; j--) {
			results.add(matrix[ex][j]);
		}
		for (int i = ex; i > sx; i--) {
			results.add(matrix[i][sy]);
		}
		spirals(matrix, sx + 1, sy + 1, ex - 1, ey - 1, results);
	}
	
    public boolean containsDuplicate(int[] nums) {
    	if(nums == null || nums.length == 0) return false;
    	HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    	for(int i = 0; i< nums.length;i++){
    		if(!map.containsKey(nums[i])) {
    			map.put(nums[i],1);
    		}else {
    			return true;
    		}
    	}
    	return false;
    }
    
    public boolean containsNearbyDuplicate(int[] nums, int k) {
    	if(nums == null || nums.length == 0 || k <= 0) return false;
    	HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    	int i;
    	for(i = 0 ; i<k && i<nums.length;i++){
    		if(!map.containsKey(nums[i])) {
    			map.put(nums[i],1);
    		}else {
    			return true;
    		}
    	}
    	if(i == nums.length) return false;
    	for(int j = k;j<nums.length;j++){
    		if(map.containsKey(nums[j])){
    			return true;
    		}else {
    			map.put(nums[j], 1);
    			map.remove(nums[j-k]);
    		}
    	}	
    	return false;
    }
    
    public int[][] generateMatrix(int n) {
    	int[][] m = new int[n][n];
    	fillInMatrix(m, 1, 0, 0, n-1,n-1);
    	return m;
    }
    public void fillInMatrix(int m[][],int startNum, int sx,int sy,int ex,int ey ){
    	if(sx > ex || sy > ey) return;
    	if(sx == ex && sy == ey ) {
    		m[sx][sy] = startNum; 
    		return;
    	}
    	for(int i = sy;i<ey;i++){
    		m[sx][i] = startNum++;
    	}
    	for(int i = sx;i<ex;i++){
    		m[i][ey] = startNum++;
    	}
    	for(int i = ey;i>sy;i--){
    		m[ex][i] = startNum++;
    	}
    	for(int i = ex;i>sx;i--){
    		m[i][sy] = startNum++;
    	}
    	fillInMatrix(m, startNum, sx+1, sy+1, ex-1, ey-1);
    }
    
    public int majorityElementI_1(int []nums){
    	if(nums == null || nums.length == 0) return -1;
    	int[] bits = new int[33];
    	int result = 0;
    	for(int i = 0; i< nums.length;i++){
    		int a = nums[i];
    		if(nums[i] < 0){
    			bits[32] = 1;
    			a = -nums[i];
    		}
    		int k = 0;
    		while( a > 0){
    			if((a & 1) > 0 ) bits[k]++;
    			k++;
    			a >>= 1;
    		}    		
    	}
    	for(int i = 0; i<32;i++){
    		if(bits[i] > (nums.length/2)){
    			result += Math.pow(2, bits[i]);
    		}
    	}
    	if(bits[32] > (nums.length/2)) result = -result;
    	return result;
    }
    public List<Integer> majorityElementII(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return list;
        int candidate1 = 0,candidate2 = 1,count1 = 0,count2 = 0;
        for(int i = 0;i<nums.length;i++){
        	if(nums[i] == nums[candidate1]) {
        		count1++;
        	}else if (nums[i] == nums[candidate2]){
        		count2++;
        	}else if(count1 == 0){
        		count1 = 1;
        		candidate1 = i;
        	}else if(count2 == 0 ){
        		count2 = 1;
        		candidate2 = i;
        	}else {
        		count1--; 
        		count2--;
        	}
        } 
        if(count1 > (nums.length/3) ){
        	list.add(nums[candidate1]);
        }
        if(count2 > (nums.length/3) ){
        	list.add(nums[candidate2]);
        }
        return list;
    }
}
